1. Field of the Invention
The invention relates generally to data processing, and more particularly, to arbitration among units of data.
2. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands.
To meet the new demands, purpose-built routers have been designed with components optimized for routing. These routers not only handle higher line rates and higher network traffic volume, but they also add functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives packets. The packets may arrive and depart on a number of associated channels. The channels of data may have different bandwidths associated with them, and purpose-built routers may process data based on these channel bandwidths.
It may be desirable to perform weighted arbitration for access to a “shared resource” among units of data (more generically, “requesters” of the shared resource) according to channel bandwidths associated with the units of data. For example, a first group of data (e.g., from a first channel) may have a first associated bandwidth and a second group of data (e.g., from a second channel) may have a second associated bandwidth. It may be desirable to arbitrate fairly (i.e., round robin) within the two groups of data, but to output data from the two groups in proportion to their bandwidths. If the first bandwidth is twice the second bandwidth, for example, units of data from the first group should be output twice as often as units of data from the second group.
FIG. 1 is a diagram illustrating an arbiter 100 for performing weighted round robin arbitration among data units according to channel bandwidths associated with the data units. Arbiter 100 may include a table 110 and a counter 120. Table 110 may contain all data to be arbitrated among. Data associated with higher-bandwidth channels may be distributed more frequently throughout table 110. For example, data units from a channel with a bandwidth ten times greater than that of another channel may appear ten times as often in the table as data units from the other channel. To ensure fair arbitration among data units associated with a given channel bandwidth, those data units should be uniformly spaced throughout table 110.
Counter 120 may be configured to sequentially step through table 110 at periodic intervals and cause data at the current location to be output. When counter 120 reaches the end of table 110, it may begin traversing table 110 at the other end. Such a sequential traversal of table 110 results in fair (i.e., round robin) arbitration among the elements in table 110. Causing the data to be distributed throughout table 110 with a frequency proportional to its channel bandwidth results in a weighting of the arbitration outputs according to their associated channel bandwidths.
The size and complexity of arbiter 100 shown in FIG. 1, however, may increase with both the number of different bandwidths and the ratio of the highest bandwidth to the lowest bandwidth. For example, if this ratio is 50, then fifty elements in table 110 would be needed for the higher bandwidth channel to every one element for the lower bandwidth channel.
Thus, there exists a need for a weighted arbiter that efficiently handles data at a number of different bandwidths and ratios of bandwidths.